#include <bits/stdc++.h>

using namespace std;
class LRUCache
{
public:
    LRUCache(int capacity)
        : _capacity(capacity)
    {
    }

    int get(int key)
    {
        //找不到
        if (m.find(key) == m.end())
        {
            return -1;
        }
        //找到后将当前的值移到链表最前面
        keys.push_front({key, (*(m[key])).second});
        keys.erase(m[key]);
        m[key] = keys.begin();
        return (*(m[key])).second;
    }

    void put(int key, int value)
    {
        //找不到，添加进链表和哈希桶
        if (m.find(key) == m.end())
        {
            keys.push_front({key, value});
            m.insert({key, keys.begin()});
            // 元素太多 删掉链表的最后一个元素
            if (keys.size() > _capacity)
            {
                m.erase(keys.back().first);
                keys.pop_back();
            }
        }
        //找到了修改值
        else
        {
            keys.push_front({key, value});
            keys.erase(m[key]);
            m[key] = keys.begin();
        }
    }

private:
    list<pair<int, int>> keys;
    int _capacity;
    unordered_map<int, list<pair<int, int>>::iterator> m;
};